package com.zhangxiaofanfan.hotcode.third;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * TODO
 *
 * @author zhangxiaofanfan
 * @date 2024-05-24 17:07:19
 */
public class HotCode017 {
    public static void main(String[] args) {
        int[] nums = {1,2,3,4};
        HotCode017 hotCode017 = new HotCode017();
        System.out.println(hotCode017.firstMissingPositive(nums));
    }

    public int firstMissingPositive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 1;
        }
        Map<Integer, Deque<Integer>> mapFront = new HashMap<>();
        Map<Integer, Deque<Integer>> mapBack = new HashMap<>();
        for (int num : nums) {
            if (num <= 0) {
                continue;
            }
            if (!mapFront.containsKey(num) && !mapBack.containsKey(num)) {
                Deque<Integer> deque = new ArrayDeque<>();
                deque.add(num);
                mapFront.put(num - 1, deque);
                mapBack.put(num + 1, deque);
            } else if (mapFront.containsKey(num) && !mapBack.containsKey(num)) {
                Deque<Integer> deque = mapFront.remove(num);
                deque.addFirst(num);
                mapFront.put(num - 1, deque);
            } else if (!mapFront.containsKey(num) && mapBack.containsKey(num)) {
                Deque<Integer> deque = mapBack.remove(num);
                deque.addLast(num);
                mapBack.put(num + 1, deque);
            } else {
                Deque<Integer> dequeFront = mapFront.remove(num);
                Deque<Integer> dequeBack = mapBack.remove(num);
                dequeBack.addLast(num);
                dequeBack.addAll(dequeFront);
                mapFront.put(dequeBack.getFirst() - 1, dequeBack);
                mapBack.put(dequeBack.getLast() + 1, dequeBack);
            }
        }
        for (Deque<Integer> deque : mapFront.values()) {
            if (deque.getFirst() <= 1 && deque.getLast() >= 1) {
                return deque.getLast() + 1;
            }
        }
        return 1;
    }
}
